package com.algorithm.sevenhundred2eighthundred;

/**
 * @author: tzj
 * @create: 2021-05-27
 **/
public class MinCostClimbingStairs_746 {

    public static void main(String[] args) {
        int[] cost = {1, 100, 1, 1, 1, 100, 1, 1, 100, 1};
        System.out.println(minCostClimbingStairs(cost));
    }

    public static int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int prev = 0, curr = 0;
        // dp[i]=min(dp[i−1]+cost[i−1],dp[i−2]+cost[i−2])
        for (int i = 2; i <= n; i++) {
            int next = Math.min(curr + cost[i - 1], prev + cost[i - 2]);
            prev = curr;
            curr = next;
        }
        return curr;
    }
}
